package 简单.前缀和与差分;

import java.util.Arrays;

/**
 * 你有一个炸弹需要拆除，时间紧迫！你的情报员会给你一个长度为 n 的 循环 数组 code 以及一个密钥 k 。
 * 为了获得正确的密码，你需要替换掉每一个数字。所有数字会 同时 被替换。
 * 如果 k > 0 ，将第 i 个数字用 接下来 k 个数字之和替换。
 * 如果 k < 0 ，将第 i 个数字用 之前 k 个数字之和替换。
 * 如果 k == 0 ，将第 i 个数字用 0 替换。
 * 由于 code 是循环的， code[n-1] 下一个元素是 code[0] ，且 code[0] 前一个元素是 code[n-1] 。
 * 给你 循环 数组 code 和整数密钥 k ，请你返回解密后的结果来拆除炸弹！
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/defuse-the-bomb
 */
public class 拆炸弹_1652 {

    public static void main(String[] args) {

        System.out.println(Arrays.toString(decrypt(new int[]{2, 4, 9, 3}, -2)));

    }

    /**
     * 前缀和
     *
     * @param code
     * @param k
     * @return
     */
    public static int[] decrypt(int[] code, int k) {
        int[] dp = new int[code.length + Math.abs(k)];
        int[] ans = new int[code.length];
        if (k == 0) {
            return ans;
        } else if (k > 0) {
            dp[0] = code[0];
            int codeIdx = 1, dpIdx = 1;
            while (dpIdx < dp.length) {
                dp[dpIdx] = dp[dpIdx - 1] + code[codeIdx];

                dpIdx++;
                codeIdx++;
                if (codeIdx >= code.length) {
                    codeIdx = 0;
                }
            }

            for (int i = 0; i < ans.length; i++) {
                ans[i] = dp[i + k] - dp[i];
            }
        } else {
            // 逆向思维
            dp[0] = code[code.length - 1];
            int codeIdx = code.length - 2, dpIdx = 1;
            while (dpIdx < dp.length) {
                dp[dpIdx] = dp[dpIdx - 1] + code[codeIdx];

                dpIdx++;
                codeIdx--;
                if (codeIdx < 0) codeIdx = code.length - 1;
            }

            for (int i = 0; i < ans.length; i++) {
                int j = code.length - 1 - i;
                ans[i] = dp[j - k] - dp[j];
            }

        }
        return ans;
    }

    // TODO 滑动窗口

}
